package com.zjsru.plan2024.oneday;

/**
 * @Author: cookLee
 * @Date: 2024-01-04
 * 被列覆盖的最多行数
 */
public class MaximumRows {

    /**
     * 主
     * \
     * 输入：matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2
     * 输出：3
     * 解释：
     * 图示中显示了一种覆盖 3 行的可行办法。
     * 选择 s = {0, 2} 。
     * - 第 0 行被覆盖，因为其中没有出现 1 。
     * - 第 1 行被覆盖，因为值为 1 的两列（即 0 和 2）均存在于 s 中。
     * - 第 2 行未被覆盖，因为 matrix[2][1] == 1 但是 1 未存在于 s 中。
     * - 第 3 行被覆盖，因为 matrix[2][2] == 1 且 2 存在于 s 中。
     * 因此，可以覆盖 3 行。
     * 另外 s = {1, 2} 也可以覆盖 3 行，但可以证明无法覆盖更多行。
     * \
     * 输入：matrix = [[1],[0]], numSelect = 1
     * 输出：2
     * 解释：
     * 选择唯一的一列，两行都被覆盖了，因为整个矩阵都被覆盖了。
     * 所以我们返回 2 。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MaximumRows maximumRows = new MaximumRows();
        int[][] matrix = new int[][]{{0,0,0},{1,0,1},{0,1,1},{0,0,1}};
        int numSelect = 2;
        System.out.println(maximumRows.maximumRows(matrix, numSelect));
    }

    public int maximumRows(int[][] matrix, int numSelect) {
        int m = matrix.length;
        int n = matrix[0].length;
        //用于存储每行的二进制掩码
        int[] mask = new int[m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //获取每行每一位数的相加的值作为二进制掩码
                mask[i] += matrix[i][j] << (n - j - 1);
            }
        }

        int res = 0;
        int cur = 0;
        int limit = (1 << n);
        while (++cur < limit) {
            //它检查当前二进制值 cur 中选定元素（设为1的位/bitCount）的数量是否等于 numSelect
            if (Integer.bitCount(cur) != numSelect) {
                continue;
            }
            int t = 0;
            //计算二进制掩码是当前二进制值 cur 的子集的行数。
            for (int j = 0; j < m; j++) {
                if ((mask[j] & cur) == mask[j]) {
                    ++t;
                }
            }
            res = Math.max(res, t);
        }
        return res;
    }

}
